package anthology.interview;

import java.util.ArrayList;
import java.util.List;

//https://leetcode.cn/problems/chuan-di-xin-xi/description/
public class LCP_07传递信息{
    class Solution {
        int ways,n,k;
        List<List<Integer>> edges;
        public int numWays(int n, int[][] relation, int k) {
            this.n = n;
            this.k = k;
            edges = new ArrayList<List<Integer>>();
            for(int i=0; i<n; i++){
                edges.add(new ArrayList<Integer>());
            }
            for(int[] edge : relation){
                edges.get(edge[0]).add(edge[1]);
            }
            dfs(0,0);
            return ways;
        }
        public void dfs(int index,int steps){
            if(steps == k){
                if(index == n-1){
                    ways++;
                }
                return;
            }
            List<Integer> list = edges.get(index);
            for(int nextIndex : list){
                dfs(nextIndex, steps+1);
            }
        }
    }
}
